import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 394. 字符串解码
 */
public class Solution_394 {
    /**
     * 精选题解：辅助栈
     * <p>
     * 时间复杂度：O(N)，一次遍历字符串
     * <p>
     * 空间复杂度：O(N)，栈空间
     */
    public String decodeString(String s) {
        StringBuilder builder = new StringBuilder();
        int multi = 0;
        Deque<Integer> multiStack = new ArrayDeque<>();
        Deque<String> builderStack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '[') {
                // 当 c 为 [ 时，将当前 multi 和 builder 入栈，并分别置空置 0
                multiStack.push(multi);
                builderStack.push(builder.toString());
                multi = 0;
                builder = new StringBuilder();
            } else if (c == ']') {
                // 当 c 为 ] 时，stack 出栈，拼接字符串
                StringBuilder temp = new StringBuilder();
                int curMulti = multiStack.pop();
                for (int i = 0; i < curMulti; i++) {
                    temp.append(builder);
                }
                builder = new StringBuilder(builderStack.pop() + temp);
            } else if (c >= '0' && c <= '9') {
                // 当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算
                multi = multi * 10 + Integer.parseInt(c + "");
            } else {
                // 当 c 为字母时，在 builder 尾部添加 c
                builder.append(c);
            }
        }
        return builder.toString();
    }

    public static void main(String[] args) {
        Solution_394 solution = new Solution_394();
        String ans = solution.decodeString("3[a]2[bc]");
        System.out.println(ans);
        ans = solution.decodeString("3[a2[c]]");
        System.out.println(ans);
    }
}
